174. Dungeon Game - LeetCode Solution

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])

        memo = [[[None] * 2 for _ in range(n)] for _ in range(m)] 
        
        def check(h, i, j):
            if memo[i][j][0] and h >= memo[i][j][0]:
                return True
            if memo[i][j][1] and h <= memo[i][j][1]:
                return False
            if h <= 0:
                return False
              
                
            result = None
            
            
            
            if i == m-1 and j == n-1:
                result =  h + dungeon[i][j] > 0
            elif i == m-1:
                result = check(h + dungeon[i][j], i, j+1)
            elif j == n-1:
                result = check(h + dungeon[i][j], i+1, j)
            else:
                result = check(h + dungeon[i][j], i+1, j) or check(h + dungeon[i][j], i, j+1)
            
            if result: 
                memo[i][j][0] = h
                return True
            else:
                memo[i][j][1] = h
                return False

            
        low, high = 0, 2**31
        while low < high:
            mid = low + (high-low)//2
            if check(mid, 0, 0):
                high = mid
            else:
                low = mid + 1

        return low